package 力扣.排序.快速排序;

public class 只出现一次的数II_137 {
    /**
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
     * 请你找出并返回那个只出现了一次的元素。

     */
    //三路切分
    public int singleNumber(int[] nums) {
        if (nums == null){
            return 0;
        }
        int len = nums.length;
        return qk(nums,0,len);
    }

    private int qk(int[] nums, int b, int e) {
        if (b  >= e){
            return 0;
        }
        int m = b + ((e - b) >> 1);
        int x = nums[m];

        int l = b,i = b,r = e - 1;
        while (i <= r){
            if (nums[i] < x){
                swap(nums,l++ ,i++);
            }else if (nums[i] == x){
                i++;
            }else{
                swap(nums, i, r--);
            }
        }
        if (i - l == 1){//只有一个，正好是中间元素
            return x;
        }else if (((l - b) % 3) != 0){//左边不是三的倍数
            return qk(nums, b, l);
        }else return qk(nums, i, e);//右边

    }
    private void swap(int[] nums,int i,int j){
        int p = nums[i];
        nums[i] = nums[j];
        nums[j] = p;
    }

    public int singleNumber4(int[] nums) {
         if (nums == null){
             return 0;
         }
         return qk2(nums,0,nums.length);
    }

    private int qk2(int[] nums, int b, int e) {
        if (b + 1 >= e){//只剩一个数字
            return nums[b];
        }
        int m = b + ((e - b) >> 1);
        int x = nums[m];
        int l = b,i = b,r = e - 1;
        while (i <= r){
            if (nums[i] < x){
                swap(nums, i++, l++);
            }else if (nums[i] == x){
                i++;
            }else{
                swap(nums, i, r--);
            }
        }
        if (i - l == 1){//在中间
            return x;
        }else if ((l - b) % 3 != 0){//说明在左区间
            return qk2(nums, b, l);
        }else {//在右区间
            return qk2(nums, i, e);
        }
    }
}
